#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

// auto inc init val
int work_id_inc = 1;

// 时间片
int timelen = 8;

// simple_turn_timer timer
int simple_turn_timer = 0;
int simple_turn_count = 0;

// define program 
struct Work{
  int id, ht, ts; //进程id, 优先级, 到达时间 timeslicen
  int st, ed; // start time, end time
  int cpuw, iow, cput, iot; // cpu wait io wait cput cost io cost
  int cpust, cpued, iost, ioed;
  bool in_wait, is_ok, working; // progress status
  bool is_first_cpu; // 标记是否是第一次cpu执行， 统计cpu开始执行时间
  int  page_access_times, page_lack_of, page_lack_percent; // 页面访问次数,  页面缺页次数，页面缺页率
  vector<int> jobs; // 页面访问序列 
  int sgp;// segment point 
  friend ostream & operator << (ostream &out,const Work &w) {
	  out << w.id << " " << w.ht << " " << (w.jobs).size() << " ";
	  for (auto x : w.jobs){
		  out << x<< " ";
	  }
	  out << endl;
    return out; }
  bool operator < (const Work &w)const {
    return ht < w.ht;
  }
  bool operator == (Work* w)const {
    return id < w->id;
  }
};

// cpu, io queue
vector<Work*> qwait;
// queue<Work> qok;

// cpu
bool cpu;
void datacreate(int n){
  if ( n > 10) {
    cout << "进程数量不能大于10" << endl;
    exit(1);
  }
  fstream f ("job", ios::out);
  vector<Work> jobs;
  f << n << endl;
  for (int i = 0; i < n; i++){
    Work w = {.id=work_id_inc++,.ht = rand() % 1000,};
    int j = rand() % 31 + 20;
    for (int k = 0; k < j; k++){
    	(w.jobs).push_back(rand() % 11 + 10);
    }
    jobs.push_back(w);
  }
  sort(jobs.begin(), jobs.end());
  for (auto x: jobs){
    f << x;
  }
  f.close();
}

void init(int n){
  datacreate(n);
}

// [x] 假定缺页中断，耗费单位时间忽略不计算。
// [ ] 假定缺页中断消耗100单位时间，时间片只有20单位时间，怎么办
// [ ] 假定缺页中断消耗10单位时间，1号进程，在15时刻发启缺页申请, 处理的话一个时间片不够，不处理，又浪费

// 处理页面访问
vector<unordered_map<int,int>> *pagecache = new vector<unordered_map<int,int>>(11);
// 页表计数器
int page_counter[11];

void fifo(Work* const cpuworkingWork,const int no, const int pageno, const int physize){
	unordered_map<int, int> &m = (*pagecache)[no];
	if (m[pageno] == 0){

		cout << cpuworkingWork->id << " 号进程发生缺页中断" << "当前缺页次数 " << cpuworkingWork->page_lack_of << endl;
		cpuworkingWork->page_lack_of++;
		m[pageno] = ++page_counter[no];
		if (page_counter[no] > physize){
			pair<int, int> tmp = {0, 0}; 
			for (auto &x : m){ if (tmp.second < x.second){ tmp = x; }; cout << "fi " << x.first << " se " << x.second; }
			for (auto &x : m){ if (tmp.second > x.second){ tmp = x; } }
			cout << endl << "被删除的元素是" << tmp.first << endl; 
			((*pagecache)[no]).erase(((*pagecache)[no]).find(tmp.first));
			m[pageno] = page_counter[no]--;
		}
	}

	vector<pair<int,int>> res;
	for (auto x : m){ res.push_back(x); };
	sort(res.begin(),res.end(),[](auto &left, auto &right) {
		return left.second > right.second;
	});
	for (auto &x : res) { cout << x.first << " ";}
	cout << endl;
}
void lru(Work* const cpuworkingWork ,const int no, const int pageno, const int physize){
	unordered_map<int, int> &m = (*pagecache)[no];
	if (m[pageno] != 0){ 
		for (auto &x : m){if (pageno != x.first){x.second ++;}}
		m[pageno] = 1;
	} else {
		// 发生缺页中断
		cpuworkingWork->page_lack_of++;
		cout << cpuworkingWork->id << " 号进程发生缺页中断" << "当前缺页次数 " << cpuworkingWork->page_lack_of << endl;
		m[pageno] = 1;
		if (m.size() > physize){
			pair<int, int> tmp = {0, 0}; 
			for (auto &x : m){ if (tmp.second < x.second){ tmp = x; }; cout << "fi " << x.first << " se " << x.second; }
			cout << endl << "被删除的元素是" << tmp.first << endl; 
			m.erase(tmp.first);
		}
	}
	vector<pair<int,int>> res;
	for (auto x : m){ res.push_back(x); };
	sort(res.begin(),res.end(),[](auto &left, auto &right) {
		return left.second < right.second;
	});
	for (auto &x : res) { cout << x.first << " ";}
	cout << endl;
}
void handle_page_req(Work* const cpuworkingWork,const int no,const int pageno,const int physize, int type){
	switch (type) {
	   case 1: { fifo(cpuworkingWork ,no, pageno, physize); break;}
	   case 2: { lru(cpuworkingWork, no, pageno, physize); break;}
	  default: { lru(cpuworkingWork, no, pageno, physize); break;}	
	}
}
void test_page_handler(Work* const cpuworkingWork){
	vector<int> res = {2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2};
	for (auto &x : res){ handle_page_req(cpuworkingWork ,1,x,4,2); }
}

void test_page_handler2(Work* const cpuworkingWork){
	vector<int> res = {2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2};
	for (auto &x : res){ handle_page_req(cpuworkingWork ,1,x,4,1); }
}
// 读取数据
vector<Work*> jobs;
void input(){
	fstream r("job", ios::in);
	int n;
	r >> n;
	
	while (n -- ) {
		Work *t = new Work{};
		int jobszie;
		r >> t->id >> t->ht >> jobszie;
		while (jobszie--) {
			int a; r >> a;
			t->jobs.push_back(a);
		}
		jobs.push_back(t);
	}
}

// simple_turn
void simple_turn(const int physize, const int type){
	// for (auto x:jobs){ cout << *x; }
	Work *cpuworkingWork = nullptr;
	bool cpu = false;
	bool complete = false;
	for (int i = 0; i < 9990; i ++){
		if (cpu && cpuworkingWork != nullptr){
			Work* t = cpuworkingWork;
			cout << "当前时间是 " << simple_turn_count << " " << cpuworkingWork->id <<" 号进程" 
			<< "正在处理序列 " << t->sgp << " 序列号 " << cpuworkingWork->jobs[t->sgp - 1] << "还剩下 " 
			<< t->jobs.size() - t->sgp - 1 << endl;
			handle_page_req(cpuworkingWork ,t->id,t->jobs[t->sgp++], physize, type);
			if (t->sgp >= t->jobs.size()){
				cout << "当前时间是 " << simple_turn_count << " " << cpuworkingWork->id << " 号进程完成" << endl;
				complete = true;
				qwait.erase(find(qwait.begin(), qwait.end(), t));
				cpuworkingWork->working = false;
				cpuworkingWork = nullptr;
				cpu = false;
			}
			
		}
		simple_turn_timer ++ ; simple_turn_count ++ ;
		if (complete || simple_turn_timer % timelen == 0){
			simple_turn_timer = 0;
			for (auto x:jobs){
				if (x->in_wait) continue;
				if (simple_turn_count > x->ht){
					cout << x->id << " 号进程加入qwait ";
					for (auto x: qwait) {cout << x->id << " working " << x->working << " "; };
					cout << endl;
					qwait.push_back(x);
					x->in_wait = true;
				}
			}
			if (cpu && cpuworkingWork != nullptr){
				cout << cpuworkingWork->id <<  "号进程" <<" cpu 锁释放"; 
				cpuworkingWork->working = false;
				qwait.erase(find(qwait.begin(), qwait.end(), cpuworkingWork));
				qwait.push_back(cpuworkingWork);
				cout << "qwait 状态";
				for (auto x: qwait) {cout << x->id << " working " << x->working << " "; }; cout << endl;
				cpu = false;
			}
			if (!cpu){
				for  (auto x: qwait){
					if (cpu) continue;
					if (x->working) continue;
					cout << x->id << "号进程开始工作 " << endl;
					cpuworkingWork = x;
					cpu = true;
				}
			}
		}
	}
}


int main (int argc, char *argv[])
{
   //init(10);
   input();
   fstream f("result", ios::out);
   // 测试页面调度
   // test_page_handler(); pass
   // test_page_handler2();
   simple_turn(3,2);
   // 输出结果
   f << "进程号 \t" << "缺页率\t" << endl;
   for (auto x: jobs){
	   f << x->id << " \t" << double(x->page_lack_of) / double(x->jobs.size()) << endl;
   }

  return 0;
}
